Computer perception and processing of visual images is important for many applications such as assembly line automation, space exploration, medicine, earth resources monitoring, computer graphics, and other spatially oriented problems. The goal is to have a machine recognize and distinguish patterns on the basis of image information. The images are usually obtained from a video scanner or solid-state camera and necessarily include many data points to enable object recognition. Moreover, picture processing operations must be applied throughout the image to extract edge, texture, and other information that can be further processed, classified, or matched against a pattern dictionary. The computationally intensive requirements of image manipulation place heavy demands on traditional computers resulting in extended processing times. Consequently, the image data processing portion of computer visual identification commonly forms a bottleneck in the image identification process.
A proposed solution to the computational bottleneck is a move away from serial processing by a general purpose computer toward parallel processing by means of a real or a simulated (pipelined) parallel image processor. Such systems are indeed capable of reducing processing time. Nonetheless, greater parallelism in processing through the use of a multitude of processors coupled in parallel necessarily inflates the initial system cost and greatly complicates implementation. On the other hand, pipelined computations minimize initial system cost, but only proceed at a rate as fast as the pipelined processor can complete individual operations and move onto successive ones.
In some system architectures there are delays that result from the communication of data rather than from the processing of data. For example, if a significant amount of data must be transferred onto or off of semiconductor chips embodying the processors, the data transfers may have to be done serially if there are not enough data transfer ports or pins on the chip for the data to be transferred completely in parallel. In these systems, the advantages of coupling a plurality of processors in parallel are curtailed since the processing time saved as a result of parallel processing is lost in waiting for data to be transferred to and from the chips.
As a modified approach to information processing, when a large amount of data is available in array form, image processing systems have been developed which respond to both global and local trends in the image data. Data structures have been proposed to facilitate such processing. Examples of such data structures are pyramids, quad-trees, hexaconal, cones, and regular decompositions. The computational bases for each of these data structures are similar. For example, a pyramid is a collection of images of the same scene arranged in levels (each with a different degree of resolution or spatial detail) with the most detailed image, i.e., the image including the most data points or elements, residing at the bottom level of the pyramid.
One of the basic operations in image processing that can be improved by using a hierarchical approach is edge detection. Ordinary edge detectors are algorithms that look only at small, local neighborhoods of a point at one time to determine if an edge of an object passes through that point. Noise from the image sensor tends to be localized and cause the use of a purely local neighborhood to produce numerous spurious edges and result in the overlooking of important edges. In a hierarchical data structure more global context can be easily utilized so that data representations of the image at various resolution levels can be combined to give reliable edge information.
The typical pyramid hierarchical data structure can be defined as a sequence of picture data arrays of the same view at different levels of resolution: EQU P=(A0, A1, A2, . . . , AL)
where A0 is a one by one array, A1 is a two-by-two array, A2 is a four by four array, and AL is a 2.sup.L by 2.sup.L array. Such a pyramid of image data is constructed by taking a 2.sup.L by 2.sup.L image and storing it into an array, AL. The array of next lowest resolution, AL-1, can be obtained by utilizing linear or non-linear functions on two-by-two blocks of image data cells or data elements in the array AL (non-overlapping blocks) to obtain values for each data cell in array AL-1. Useful functions may include, for example, an average of the two-by-two block, the maximum or minimum value in the block, the median value in the block, or other functions.
Such a pyramid data structure finds application in many areas including edge detection, hierarchical searching, region growing, statistical classification, and computer graphics. However, the utilization of a hierarchical data structure such as a pyramid does not alone solve the problems resulting from the adoption of either a parallel or pipelined processing structure. If in such a pyramid data structure, a processor is dedicated to each cell (data point or element) in the image array at each level of data resolution, the number of interconnection lines among the same level processors and between the same level processors and global neighbor processors becomes unworkable. Moreover, since there are very large numbers of processors to be interconnected, the number of communication lines increases to a point not feasible for interconnection with a single chip. Also, a one-to-one correspondence between processors and unit cells places an upper limit on the number of cells per image because of the large area and power requirements of a large plurality of such processors.
The net result is that hierarchical data structures implemented by parallel processors in one-to-one correspondence with data cells forming arrays of differing resolutions, have in the past been plagued with unresolved problems. The problems which have stood in the way of success, before the instant invention, include high cost, unreliability because of high complexity, heat dissipation problems, and limitations on data transfer rates between processor chips.